/**
 * 3
 *  
 * @Author : Ruoyu Wang
 * @DateTime : 24-9-14 下午2:26
 */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    /**
     * Note: 类名、方法名、参数名已经指定，请勿修改
     *
     *
     *
     * @param grid int整型 vector<vector<>>
     * @return int整型
     */
    int minPathSum(vector<vector<int> > &grid) {
        vector<vector<int>> f(grid.size(), vector<int>(grid[0].size(), 0));
        f[0][0] = grid[0][0];
        for (int i = 1; i < grid.size(); ++i) {
            f[i][0] = f[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < grid[0].size(); ++j) {
            f[0][j] = f[0][j - 1] + grid[0][j];
        }
        for (int i = 1; i < grid.size(); ++i) {
            for (int j = 1; j < grid[0].size(); ++j) {
                f[i][j] = min(f[i][j - 1], f[i - 1][j]) + grid[i][j];
            }
        }
        return f[f.size() - 1][f[0].size() - 1];
    }
};


int main() {
    Solution sl;
    vector<vector<int>> nums = {{1, 3, 1},
                                {1, 5, 1},
                                {4, 2, 1}};
    cout << sl.minPathSum(nums);
    return 0;
}